//Given a collection of candidate numbers (candidates) and a target number (
//target), find all unique combinations in candidates where the candidate numbers sum 
//to target. 
//
// Each number in candidates may only be used once in the combination. 
//
// Note: The solution set must not contain duplicate combinations. 
//
// 
// Example 1: 
//
// 
//Input: candidates = [10,1,2,7,6,1,5], target = 8
//Output: 
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//]
// 
//
// Example 2: 
//
// 
//Input: candidates = [2,5,2,1,2], target = 5
//Output: 
//[
//[1,2,2],
//[5]
//]
// 
//
// 
// Constraints: 
//
// 
// 1 <= candidates.length <= 100 
// 1 <= candidates[i] <= 50 
// 1 <= target <= 30 
// 
// Related Topics Array Backtracking 👍 3991 👎 108


package leetcode.editor.en;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _40_CombinationSumIi {
    public static void main(String[] args) {
        Solution solution = new _40_CombinationSumIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(candidates);
            dfs(candidates, result, target, 0, new ArrayList<>());
            return result;
        }

        private  void dfs(int[] candidates, List<List<Integer>> result, int target, int i, List<Integer> es) {
            if (target == 0) {
                result.add(new ArrayList<>(es));
                return;
            }
            if(target<0){
                return;
            }
            for (int j = i; j < candidates.length; j++) {
                if (j > i && candidates[j] == candidates[j - 1]) {
                    continue;
                }
                es.add(candidates[j]);
                dfs(candidates, result, target-candidates[j], j+1, es);
                es.remove(es.size()-1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}